#define _CRT_SECURE_NO_WARNINGS 1

void CountSort(int* a, int n)
{
	// 初始化最小值和最大值为数组的第一个元素
	int min = a[0], max = a[0];
	// 遍历数组以找出最小值和最大值
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i]; // 更新最小值
		if (a[i] > max)
			max = a[i]; // 更新最大值
	}

	// 得到需要创建count数组的个数是range
	int range = max - min + 1;
	//创建count数组
	int* count = (int*)malloc(sizeof(int) * range);

	// 检查内存分配是否成功
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	// 初始化计数数组全为0
	memset(count, 0, sizeof(int) * range);

	// 统计数据出现次数
	for (int i = 0; i < n; i++)
	{
		// 计算元素在计数数组中的索引，并增加计数
		count[a[i] - min]++;
	}

	// 排序数组
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		// 当计数数组中的计数大于0时，将元素按顺序放回原数组
		while (count[i]--)
		{
			a[j++] = i + min; // 使用min偏移量将计数数组索引映射回原数组元素
		}
	}

	// 释放动态分配的计数数组
	free(count);
}